Image processing is employed in various applications, such as in the electronic conversion of photographic images, reproduction of graphical information in a printing operation, and coding and subsequent reconstruction of digital image data in electronic communication systems. Filtering is one such processing method and includes arithmetic operations performed on numerical values representing picture data elements, also known as pixels.
An original image, consisting of a photograph or a video frame, is typically digitized as a matrix of numerical values, commonly referred to as a "spatial domain" matrix comprising image data terms. Each image data term corresponds to a particular pixel in the image and the numerical value of the image data term quantitatively describes a feature characteristic of that pixel.
A widely-used standard for practicing filtering and other processing methods is described in the reference text, "JPEG Still Image Data Compression Standard," by William B. Pennebaker and Joan L. Mitchell. In accordance with the JPEG standard, a digitized image is provided as a series of image-data matrices, usually formatted as 8.times.8 matrices, and then a transformation process is applied to produce a series of processed frequency coefficient matrices which can be stored or transmitted. An inverse transformation is applied to the processed frequency coefficient matrices and the resulting series of processed image-data matrices are recombined into a processed image. The use of standard DCT electronic processing units for performing such transformations is well-known in the relevant art.
In many applications in the field of signal and image processing, a two-dimensional Discrete Cosine Transform (DCT) is used to transform the image data into frequency coefficients, and can be expressed in shorthand notation as, EQU S(.nu.,.mu.)=C.times.s(j,i).times.C.sup.T
where, S(.nu.,.mu.) are terms in the frequency coefficient matrix,
s(j,i) are terms in the image-data matrix, PA1 C is the basis matrix, and PA1 C.sup.T is the inverse transform of the basis matrix.
The corresponding 8-point DCT for an 8.times.8 image data matrix is given by the equation, ##EQU1## where ##EQU2## for k=0 and C.sub.k =1 for k&gt;0.
A two-dimensional inverse DCT (IDCT) is used to transform frequency coefficients into image data, and can be expressed in shorthand notation as, EQU s(j,i)=C.sup.T .times.S(.nu.,.mu.).times.C
The corresponding 8-point two-dimensional IDCT is given by the equation, ##EQU3##
The series of image-data matrices provided for processing is obtained from the original image by a method which first formats the original image pixels into a group of image-data blocks. Each block comprises an array of image-data terms, for example, an array of sixty-four terms in eight rows and eight columns. At least two alternative block configurations are discussed in the relevant art.
In one configuration, the image data matrix is simply partitioned into an array of "nonoverlapped" image-data blocks. Each block contains some of the image data terms from the image data matrix, and no block contains pixel data that is common to an adjacent block. The nonoverlapped image data block configuration is specified for image processing methods performed according to Joint Photographic Experts Group (JPEG) standard ISO DIS 10918-1. An array of image-data blocks in which each block contains no pixel data in common with an adjacent block is herein denoted as a standard spatial-domain array.
In an alternative, "overlapped" configuration, each block in the image data array has one or more rows and columns of image data terms in common with image-data terms found in one or more rows and columns of adjacent blocks. Image data terms are thus shared, or duplicated, among adjacent blocks in the array. It has been found that because image data is thus shared, certain image processing procedures show improved results when performed on blocks which have been overlapped, in comparison to blocks which have not been overlapped. An array of image-data blocks in which each block contains pixel data in common with adjacent blocks is herein denoted as an extended spatial-domain array.
The original image can also be defined by a set of frequency coefficient matrices, where the matrix terms are obtained by a mathematical transformation of blocks of original image data terms. These frequency-coefficient matrices can be derived from both overlapped and nonoverlapped image data blocks. Filtering operations are typically performed by mask multiplying a filter matrix with a frequency-coefficient matrix. For a particular filtering operation, one of the standard and the extended spatial-domain array configurations may be the preferred format. In such cases, a conventional filtering method includes applying a DCT, mask multiplying, and applying an IDCT.
However, in processing methods in which two or more filtering operations are performed, it may be necessary to execute one or more operations using extended-array matrices in addition to using standard array matrices. In such cases, it becomes necessary to convert between the standard and extended configurations so that all filtering operations can be accomplished.
The conventional process of converting frequency coefficients between standard and extended array configurations comprises the circuitous procedure of i) transforming frequency coefficients into image data by the application of an IDCT, ii) overlapping (or unoverlapping) the image-data blocks obtained, and iii) transforming the image data obtained into frequency coefficients by the application of a DCT. This process is inherently inefficient because of the reciprocal DCT/IDCT computations required. What is needed is a more efficient, direct method for converting between a standard-array and an extended-array matrix configuration.
It is therefore an object of the present invention to provide a method for efficiently converting a given array of frequency-transformed image data matrices between two different formats: one format in which the given matrices are derived from a standard array of nonoverlapped blocks of image data, and another format in which the given matrices are derived from an extended array of overlapped blocks of the same image data.
It is a further object of the present invention to provide such a method which performs the conversion between formats with greater computational efficiency than is typically found in the relevant art.
It is a further object of the present invention to provide a such method which is implemented in the frequency domain alone and does not require either a transform operation or the inverse transform operation for implementation.
It is a further object of the present invention to provide an apparatus for performing the conversion of an array of frequency-coefficient matrices between such formats.
It is a still further object of the present invention to provide such an apparatus by utilizing a standard DCT electronic processing unit.
Other objects of the invention will, in part, appear hereinafter and, in part, be apparent when the following detailed description is read in connection with the drawings.